package com.leetcode.algorithm.y22.m08.w5;

import java.util.Arrays;

/**
 * 455. 分发饼干
 * 
 * https://leetcode.cn/problems/assign-cookies/
 * 
 * @author jie.deng
 *
 */
class Question0455Solution01 {

	// 贪心算法
	public int findContentChildren(int[] g, int[] s) {
		// 前提条件：每个孩子最多只能给一块饼干
		// 局部最优：大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个
		// 全局最优：喂饱尽可能多的小孩
		Arrays.sort(g);
		Arrays.sort(s);
		int idxG = g.length - 1;
		int idxS = s.length - 1;
		int cnt = 0;
		while (idxG >= 0 && idxS >= 0) {
			if (s[idxS] >= g[idxG]) {
				idxS--;
				idxG--;
				cnt++;
			} else {
				idxG--;
			}
		}
		return cnt;
	}

}